package study.sort1;

import java.util.Arrays;

public class QuickSort {

    static int count = 1;

    public static void main(String[] args) {
        int[] arr = new int[]{4,7,6,5,3,2,8,1};
//        int[] arr = new int[]{4,7,3,5,6,2,8,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));


        System.out.println("\n\n");
        count = 1;
        int[] arr1 = new int[]{4,7,6,5,3,2,8,1};
//        int[] arr1 = new int[]{4,7,3,5,6,2,8,1};
        sort1(arr1);
        System.out.println(Arrays.toString(arr1));
    }

    static void sort(int[] arr) {
        if(arr == null || arr.length <= 1)
            return;
        sort(arr, 0, arr.length - 1);
    }

    static void sort1(int[] arr) {
        if(arr == null || arr.length <= 1)
            return;
        sort1(arr, 0, arr.length - 1);
    }

    /**
     * 双边循环
     * @param arr
     * @param start
     * @param end
     */
    private static void sort(int[] arr, int start, int end) {
        if(start >= end || start >= arr.length)
            return;
        int pivot = arr[start];
        int i = start + 1;
        int j = end;
        while(i <= j) {
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            while (i <= j && arr[i] < pivot) {
                i++;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i++;
                j--;
            }
        }
        if(pivot > arr[j]) {
            arr[start] = arr[j];
            arr[j] = pivot;
        }
        System.out.printf("第%d轮后：%s\n", count++, Arrays.toString(arr));
        sort(arr, start, j - 1);
        sort(arr, j + 1, end);
    }

    /**
     * 单边循环
     * @param arr
     * @param start
     * @param end
     */
    private static void sort1(int arr[], int start, int end) {
        if(start >= end || start >= arr.length)
            return;
        int pivot = arr[start];
        int mark = start;
        for(int i = start + 1; i <= end; i ++) {
            if(arr[i] < pivot && arr[++ mark] > arr[i]) {
                int t = arr[i];
                arr[i] = arr[mark];
                arr[mark] = t;
            }
        }
        if(arr[mark] < pivot) {
            arr[start] = arr[mark];
            arr[mark] = pivot;
        }
        System.out.printf("第%d轮后：%s\n", count++, Arrays.toString(arr));
        sort1(arr, start, mark - 1);
        sort1(arr, mark + 1, end);
    }
}
